package com.jia.interviewPro;

public class Pro0404 {

    boolean flag = true;
    //dfs 后续遍历
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return flag;
    }
    private int dfs(TreeNode node) {
        if(node == null) {return 0;}
        int left = dfs(node.left);
        int right = dfs(node.right);
        if(Math.abs(left - right) > 1) {
            flag = false;
        }
        return Math.max(left, right) + 1;
    }


    public boolean isBalanced2(TreeNode root) {
        return root == null || (Math.abs(depth(root.left)-depth(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right));
    }
    private int depth(TreeNode node) {
        return node == null? 0 : Math.max(depth(node.left), depth(node.right)) + 1;
    }
}
